package vip.zhenzicheng.algorithm.leetcode.bit;

/**
 * <a href="https://leetcode.cn/problems/counting-bits/">比特位计数 [简单]</a>
 * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
 * 提示：
 * 0 <= n <= 105
 * 进阶：
 * 很容易就能实现时间复杂度为 O(n log n) 的解决方案，你可以在线性时间复杂度 O(n) 内用一趟扫描解决此问题吗？不使用内置函数
 *
 * @author zhenzicheng
 * @date 2022-06-10 14:18
 */
public class CountingBits_338 {

  // 使用位运算
  // public int[] countBits(int n) {
  //     int[] bits = new int[n + 1]; // 提干要求
  //     for (int i = 1, lastBitCount; i<= n; i++) { // 从第二个数开始，因为新数组长度为比原数组大1
  //         lastBitCount = i & (i - 1); // N & (N - 1) 清除最低位的1
  //         bits[i] = bits[lastBitCount] + 1; // 计算出 (N - 1) 中1的个数后再加回1
  //     }
  //     return bits;
  // }

  // 利用奇偶性
  public int[] countBits(int n) {
    int[] bits = new int[n + 1];
    for (int i = 1; i <= n; i++) {
      bits[i] = ((i & 1) == 1 ? bits[i - 1] + 1 : bits[i >> 1]); // 奇数总比上一个奇数1的个数多一个，偶数总是与除2后的1的个数相同
    }
    return bits;
  }
}
